package com.future.offer;

import com.future.util.TreeNode;

import java.util.LinkedList;

/**
 * Description: 剑指 Offer 37. 序列化二叉树
 * leetcode/img/offer/Solution_37.png
 *
 * @author weiruibai.vendor
 * Date: 2023/1/6 10:19
 */
public class Solution_37 {

    private static Codec instance = new Codec();

    public static void main(String[] args) {
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.right = new TreeNode(3);
        root.right.left = new TreeNode(4);
        root.right.right = new TreeNode(5);
        String serialize = instance.serialize(root);
        TreeNode deserialize = instance.deserialize(serialize);
        System.out.println();
    }

}

/**
 * 输入：root = [1,2,3,null,null,4,5]
 * 输出：[1,2,3,null,null,4,5]
 */
class Codec {

    // Encodes a tree to a single string.
    public String serialize(TreeNode root) {
        StringBuilder sb = new StringBuilder();
        if (root == null) {
            return null;
        }
        preSearch(root, sb);
        return sb.toString();
    }

    private void preSearch(TreeNode root, StringBuilder sb) {
        if (root == null) {
            sb.append(".null");
            return;
        }
        sb.append("." + root.val);
        preSearch(root.left, sb);
        preSearch(root.right, sb);
    }

    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        if (data == null) {
            return null;
        }
        LinkedList<String> list = new LinkedList<>();
        String[] split = data.split("\\.");
        for (String str : split) {
            if ("".equals(str)) continue;
            list.add(str);
        }
        return buildTreeNode(list);
    }

    private TreeNode buildTreeNode(LinkedList<String> list) {
        String pop = list.pop();
        if (list.size() == 0 || pop.equals("null")) {
            return null;
        }
        TreeNode root = new TreeNode(Integer.valueOf(pop));
        root.left = buildTreeNode(list);
        root.right = buildTreeNode(list);
        return root;
    }
}